{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Rotate Matrix LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rotate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #旋转矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一幅由 <code>N × N</code> 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。</p>\n",
    "\n",
    "<p>不占用额外内存空间能否做到？</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "给定 <strong>matrix</strong> = \n",
    "[\n",
    "  [1,2,3],\n",
    "  [4,5,6],\n",
    "  [7,8,9]\n",
    "],\n",
    "\n",
    "<strong>原地</strong>旋转输入矩阵，使其变为:\n",
    "[\n",
    "  [7,4,1],\n",
    "  [8,5,2],\n",
    "  [9,6,3]\n",
    "]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "给定 <strong>matrix</strong> =\n",
    "[\n",
    "  [ 5, 1, 9,11],\n",
    "  [ 2, 4, 8,10],\n",
    "  [13, 3, 6, 7],\n",
    "  [15,14,12,16]\n",
    "], \n",
    "\n",
    "<strong>原地</strong>旋转输入矩阵，使其变为:\n",
    "[\n",
    "  [15,13, 2, 5],\n",
    "  [14, 3, 4, 1],\n",
    "  [12, 6, 8, 9],\n",
    "  [16, 7,10,11]\n",
    "]\n",
    "</pre>\n",
    "\n",
    "<p><strong>注意</strong>：本题与主站 48 题相同：<a href=\"https://leetcode-cn.com/problems/rotate-image/\">https://leetcode-cn.com/problems/rotate-image/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [rotate-matrix-lcci](https://leetcode.cn/problems/rotate-matrix-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [rotate-matrix-lcci](https://leetcode.cn/problems/rotate-matrix-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        arraylength = len(nums)\n",
    "        k = k % arraylength\n",
    "        if k == 0 or k == arraylength:\n",
    "            return nums\n",
    "\n",
    "        nums[:] = nums[-k:] + nums[:len(nums) - k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        \n",
    "        k = k%len(nums)\n",
    "        def arrReverse(arr, start, end):\n",
    "            mid = (end-start+1) // 2 \n",
    "            for i in range(mid):\n",
    "                arr[start+i] ^= arr[end-i]\n",
    "                arr[end-i] ^= arr[start+i]\n",
    "                arr[start+i] ^= arr[end-i]\n",
    "        \n",
    "        arrReverse(nums, 0, len(nums)-1-k)\n",
    "        arrReverse(nums, len(nums)-k, len(nums)-1)\n",
    "        arrReverse(nums, 0, len(nums)-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        k = k % len(nums)\n",
    "        nums_new = nums[-k:] + nums[:len(nums) - k]\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = nums_new[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        i=0\n",
    "        while(k>0):\n",
    "            i = nums.pop()\n",
    "            nums.insert(0,i)\n",
    "            k-=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        l = len(nums)\n",
    "        k = l - k % l\n",
    "        nums[:] = nums[k:] + nums[0:k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: 'List[int]', k: 'int') -> 'None':\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        k = k % len(nums)\n",
    "        nums[:] = nums[-k:] + nums[:-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        lens = len(nums)\n",
    "        k = k%lens\n",
    "        # print('k=',k)\n",
    "        nums[:] = k * [0] + nums\n",
    "        # print(nums)\n",
    "        nums[0:k] = nums[lens:k+lens]\n",
    "        # print(nums)\n",
    "        nums[:]=nums[0:lens]\n",
    "        # print(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        length = len(nums)\n",
    "        k_value = k % length\n",
    "\n",
    "        # 将元素移动到新位置与原有元素组成二元列表\n",
    "        s = length - 1\n",
    "        for i in range(len(nums)):\n",
    "            if type(nums[i]) != list:\n",
    "                nums[k_value - s - 1] = [nums[i], nums[k_value - s - 1]]\n",
    "            else:\n",
    "                nums[k_value - s - 1] = [nums[i].pop(), nums[k_value - s - 1]]\n",
    "\n",
    "            s -= 1\n",
    "\n",
    "        # 将所有列表类型元素还原为数字\n",
    "        for j in range(length):\n",
    "            nums[j] = nums[j][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        \n",
    "        length=len(nums)\n",
    "        temp=[0]*length\n",
    "        print(length)\n",
    "        for i in range(length):\n",
    "            print(nums[i])\n",
    "            temp[(i+k)%length]=nums[i]\n",
    "        for j in range(length):\n",
    "            nums[j]=temp[j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        i=0\n",
    "        while i<k:\n",
    "            s = nums.pop()\n",
    "            nums.insert(0,s)\n",
    "            i=i+1\n",
    "        for i in nums:\n",
    "            print(i)\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: 'List[int]', k: 'int') -> 'None':\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        def rotateIndex(i):\n",
    "            return (i+k)%len(nums)\n",
    "        \n",
    "        k = k% len(nums)\n",
    "        count = 0\n",
    "        for i in range(len(nums)):\n",
    "            current = i\n",
    "            prev = nums[i]\n",
    "\n",
    "            while True:\n",
    "                next = rotateIndex(current)\n",
    "                tmp = prev\n",
    "                prev = nums[next]\n",
    "                nums[next] = tmp\n",
    "                current = next\n",
    "                count+=1\n",
    "                if i == current:\n",
    "                    break\n",
    "            \n",
    "            if count >= len(nums):\n",
    "                break\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        k=k%n\n",
    "        def swap(l,r):\n",
    "            while(l<r):\n",
    "                nums[l],nums[r]=nums[r],nums[l]\n",
    "                l=l+1\n",
    "                r=r-1\n",
    "        swap(0,n-k-1)\n",
    "        swap(n-k,n-1)\n",
    "        swap(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        k = k%len(nums)\n",
    "        if len(nums) == 1 or k == 0 :\n",
    "            nums = nums\n",
    "        else:\n",
    "            nums[:] = nums[-k:] + nums[:len(nums)-k]    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        start = 0\n",
    "        end = len(nums)\n",
    "        index = end - 1\n",
    "        for i in range(start, end):\n",
    "            if i < (start + (end - start)/2) :\n",
    "                tmp = nums[i]\n",
    "                nums[i] = nums[index]\n",
    "                nums[index] = tmp\n",
    "                index -= 1\n",
    "        start = 0\n",
    "        end = k%len(nums)\n",
    "        index = end - 1\n",
    "        for i in range(start, end):\n",
    "            if i < (start + (end - start)/2) :\n",
    "                tmp = nums[i]\n",
    "                nums[i] = nums[index]\n",
    "                nums[index] = tmp\n",
    "                index -= 1\n",
    "\n",
    "        start = k%len(nums)\n",
    "        end = len(nums)\n",
    "        index = end - 1\n",
    "        for i in range(start, end):\n",
    "            if i < (start + (end - start)/2) :\n",
    "                tmp = nums[i]\n",
    "                nums[i] = nums[index]\n",
    "                nums[index] = tmp\n",
    "                index -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        length = len(nums)\n",
    "        k = k%length\n",
    "        start = 0\n",
    "        count = 0\n",
    "        while count < length:\n",
    "            cur_index = start\n",
    "            pre = nums[cur_index]\n",
    "            while True:\n",
    "                next_index = (cur_index+k)%length\n",
    "                temp = nums[next_index]\n",
    "                nums[next_index] = pre\n",
    "                pre = temp\n",
    "                cur_index = next_index\n",
    "                count += 1\n",
    "                if cur_index == start:\n",
    "                    break\n",
    "            start +=1\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        a= [0]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            a[(i+k)%len(nums)] = nums[i]\n",
    "        nums[:] = a[:]\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        idx = 0\n",
    "        csr = nums[0]\n",
    "        buf = []\n",
    "        for _ in range(len(nums)):\n",
    "            # print(buf, idx)\n",
    "            if idx in buf:\n",
    "                idx = 0\n",
    "                while idx in buf:\n",
    "                    idx += 1\n",
    "                    csr = nums[idx]\n",
    "            # print(\"new idx: \", idx, \"csr: \", csr)\n",
    "\n",
    "            buf.append(idx)\n",
    "            idx += k\n",
    "            idx %= len(nums)\n",
    "\n",
    "            nums[idx], csr = csr, nums[idx]\n",
    "            # print(nums)\n",
    "            # print(\"--------------\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums, k) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        idx = 0\n",
    "        csr = nums[0]\n",
    "        buf = []\n",
    "        for _ in range(len(nums)):\n",
    "            # print(buf, idx)\n",
    "            if idx in buf:\n",
    "                # idx = 0\n",
    "                # while idx in buf:\n",
    "                    idx += 1\n",
    "                    csr = nums[idx]\n",
    "            # print(\"new idx: \", idx, \"csr: \", csr)\n",
    "\n",
    "            buf.append(idx)\n",
    "            idx += k\n",
    "            idx %= len(nums)\n",
    "\n",
    "            nums[idx], csr = csr, nums[idx]\n",
    "            # print(nums)\n",
    "            # print(\"--------------\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        k = k%len(nums)\n",
    "        nums[:] = nums[-k :] + nums[:-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        temp = list(nums)\n",
    "        lenth = len(nums)\n",
    "        for i in range(lenth):\n",
    "            nums[(i + k) % lenth] = temp[i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return nums\n",
    "        n = len(nums)\n",
    "        k = k % n   #当k大于数组长度n时，移动k次等于移动k%n次\n",
    "        def reverse(nums, i, j):\n",
    "            left, right = i, j - 1\n",
    "            while left < right:\n",
    "                nums[left], nums[right] = nums[right], nums[left]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        reverse(nums, 0, n-k)\n",
    "        reverse(nums, n-k, n)\n",
    "        reverse(nums, 0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        length = len(nums)\n",
    "        k = k%length\n",
    "        if k==0:\n",
    "            return nums\n",
    "        iterset = set(range(k))\n",
    "        while(iterset):\n",
    "            idx = iterset.pop()\n",
    "            temp = nums[idx]\n",
    "            while(True):\n",
    "                while(idx+k<length):\n",
    "                    temp,nums[idx+k] = nums[idx+k],temp\n",
    "                    idx+=k\n",
    "                temp,nums[(idx+k)%length] = nums[(idx+k)%length],temp\n",
    "                if (idx+k)%length in iterset:\n",
    "                    iterset.remove((idx+k)%length)\n",
    "                    idx = (idx+k)%length\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        temp = {}\n",
    "        total = len(nums)\n",
    "        i = 0\n",
    "        while i < total:\n",
    "            j = (i + k) % total\n",
    "            temp[j] = nums[j]\n",
    "            if i in temp:\n",
    "                nums[j] = temp.pop(i)\n",
    "            else:\n",
    "                nums[j] = nums[i]\n",
    "            i += 1            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if n<=1:\n",
    "            return\n",
    "\n",
    "        k = k%n\n",
    "\n",
    "        def move(start, step):\n",
    "            pre = start\n",
    "            startval = nums[start]\n",
    "            nextind = pre - step\n",
    "            nextind = n + nextind if nextind < 0 else nextind\n",
    "\n",
    "            while nextind != start:\n",
    "                if pre in state:\n",
    "                    state[pre] = True\n",
    "                nums[pre] = nums[nextind]\n",
    "                pre = nextind\n",
    "                nextind = pre - step\n",
    "                nextind = n + nextind if nextind < 0 else nextind\n",
    "            nums[pre] = startval\n",
    "\n",
    "        state = {i:False for i in range(k)}\n",
    "        for i in range(k):\n",
    "            if not state[i]:\n",
    "                move(i, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return nums\n",
    "        n = len(nums)\n",
    "        done_index = set()\n",
    "        done_index.add(0)\n",
    "        count, index, temp = 1, 0, nums[0]\n",
    "        while count <= n:\n",
    "            index = (index + k) % n\n",
    "            count += 1\n",
    "            temp, nums[index] = nums[index], temp\n",
    "            if index in done_index:\n",
    "                if index + 1 < n:\n",
    "                    index += 1\n",
    "                    temp = nums[index]\n",
    "            done_index.add(index)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        if len(nums) == 0:\n",
    "            return\n",
    "        shift = k % len(nums)\n",
    "        if shift == 0:\n",
    "            return\n",
    "        shift_index_set = set([])\n",
    "        print(shift)\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            currect_index = i\n",
    "            current_v = nums[currect_index]\n",
    "            while True:\n",
    "                if currect_index not in shift_index_set:\n",
    "                    next_index = (currect_index + shift) % len(nums)\n",
    "                    tmp = nums[next_index]\n",
    "                    nums[next_index] = current_v\n",
    "                    current_v = tmp\n",
    "                    shift_index_set.add(currect_index)\n",
    "                    print(next_index, currect_index, current_v)\n",
    "                    currect_index = next_index\n",
    "                else:\n",
    "                    break\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        visited = set()\n",
    "        length = len(nums)\n",
    "        index = 0\n",
    "        n = nums[index]\n",
    "        while len(visited) < length:\n",
    "            while index not in visited:\n",
    "                new = (index + k) % length\n",
    "                n, nums[new] = nums[new], n\n",
    "                visited.add(index)\n",
    "                index = new\n",
    "            index = (index + 1) % length\n",
    "            n = nums[index]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        l = len(nums)\n",
    "        hold = nums[0]\n",
    "        temp = 0\n",
    "        index = 0\n",
    "        i = 0\n",
    "        flag = set([])\n",
    "\n",
    "        while i < l:\n",
    "            index = (index+k)%l\n",
    "            i += 1\n",
    "            if index in flag:\n",
    "                index = (index+1)%l\n",
    "                hold = nums[index]\n",
    "                i -= 1\n",
    "            else:\n",
    "                temp = nums[index]\n",
    "                nums[index] = hold\n",
    "                hold = temp\n",
    "                flag.add(index)\n",
    "            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        # b = nums[(len(nums) - k):]\n",
    "        # for i in range(len(b)-1, -1, -1):\n",
    "        #     nums.pop()\n",
    "        #     nums.insert(0, b[i])\n",
    "        class Node(object):\n",
    "            def __init__(self, value=None, prev=None, next=None):\n",
    "                self.value, self.prev, self.next = value, prev, next\n",
    "\n",
    "        class CircualDoubleLinedList(object):\n",
    "            def __init__(self, maxsize=None):\n",
    "                self.maxsize = maxsize\n",
    "                node = Node()\n",
    "                node.next, node.prev = node, node\n",
    "                self.root = node\n",
    "                self.length = 0\n",
    "            \n",
    "            def __len__(self):\n",
    "                return self.length\n",
    "\n",
    "            def headnode(self):\n",
    "                return self.root.next\n",
    "\n",
    "            def tailnode(self):\n",
    "                return self.root.prev\n",
    "                \n",
    "            def append(self, value):\n",
    "                if self.maxsize is not None and len(self) > self.maxsize:\n",
    "                    raise Exception('full')\n",
    "                node = Node(value=value)\n",
    "                tailnode = self.tailnode()\n",
    "\n",
    "                tailnode.next = node\n",
    "                node.prev = tailnode\n",
    "\n",
    "                node.next = self.root\n",
    "                self.root.prev = node\n",
    "\n",
    "                self.length += 1\n",
    "            \n",
    "            def appendleft(self, value):\n",
    "                if self.maxsize is not None and len(self) > self.maxsize:\n",
    "                    raise Exception('full')\n",
    "                \n",
    "                node = Node(value=value)\n",
    "                if self.root.next is self.root:\n",
    "                    node.next = self.root\n",
    "                    node.prev = self.root\n",
    "\n",
    "                    self.root.next = node\n",
    "                    self.root.prev = node\n",
    "                else:\n",
    "                    node.prev = self.root\n",
    "                    headnode = self.root.next\n",
    "                    node.next = headnode\n",
    "                    headnode.prev = node \n",
    "                    self.root.next = node\n",
    "                self.length += 1\n",
    "            \n",
    "            def remove(self, node):\n",
    "                if node is self.root:\n",
    "                    return\n",
    "                else:\n",
    "                    node.prev.next = node.next\n",
    "                    node.next.prev = node.prev\n",
    "            \n",
    "            def iter_node(self):\n",
    "                if self.root.next is self.root:\n",
    "                    return\n",
    "                curnode = self.root.next\n",
    "                while curnode.next is not self.root:\n",
    "                    yield curnode\n",
    "                    curnode = curnode.next\n",
    "                yield curnode\n",
    "            \n",
    "            def __iter__():\n",
    "                for node in self.iter_node():\n",
    "                    yield node.value\n",
    "            \n",
    "            def iter_node_reverse(self):\n",
    "                if self.root.prev is self.root:\n",
    "                    return Node()\n",
    "                \n",
    "                curnode = self.root.prev\n",
    "                while curnode.prev is not self.root:\n",
    "                    yield curnode\n",
    "                    curnode = curnode.prev\n",
    "                yield curnode\n",
    "            \n",
    "            def move_root(self, node_head):\n",
    "                self.root.next = node_head\n",
    "                self.root.prev = node_head.prev\n",
    "                node_head.prev.next = self.root\n",
    "                node_head.prev = self.root\n",
    "\n",
    "        if len(nums)!=0 and k !=0 and len(nums)!= k and len(nums)!=1:    \n",
    "            k = k%len(nums)\n",
    "            # k -= 1\n",
    "            doublelist_nums = CircualDoubleLinedList()\n",
    "            for i in nums:\n",
    "                doublelist_nums.append(i)\n",
    "            before_tail = doublelist_nums.tailnode()\n",
    "            before_head = doublelist_nums.headnode()\n",
    "            new_head = Node()\n",
    "            for node in doublelist_nums.iter_node_reverse():\n",
    "                if k > 0:\n",
    "                    new_head = node\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    break\n",
    "            before_tail.next = before_head\n",
    "            before_head.prev = before_tail\n",
    "            doublelist_nums.move_root(new_head)\n",
    "            doublist = [node.value for node in doublelist_nums.iter_node()]\n",
    "            for i in range(len(nums)):\n",
    "                nums[i] = doublist[i]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        \n",
    "        n = len(nums)\n",
    "        step = k % n\n",
    "        i = 0\n",
    "        count = 0\n",
    "        while count < n:\n",
    "            j = i\n",
    "            temp = nums[i]\n",
    "            nums[(i + step) % n], temp = temp, nums[(i + step) % n]\n",
    "            count += 1\n",
    "            i = (i + step) % n\n",
    "            while j != i and count < n:\n",
    "                nums[(i + step) % n], temp = temp, nums[(i + step) % n]\n",
    "                count += 1\n",
    "                i = (i + step) % n\n",
    "            if count == n:\n",
    "                break\n",
    "            i += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        k = k%len(nums)\n",
    "        nums[:] = nums[-k:]+nums[:-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        n = len(nums)\n",
    "        while k > n:\n",
    "            k = k -n\n",
    "        i = n -k\n",
    "        list1= nums[n-k:n]\n",
    "        list2 = nums[0:n-k]\n",
    "        for l in range(len(list2)):\n",
    "            nums[l+k] = list2[l]\n",
    "        for j in range(len(list1)):\n",
    "            nums[j] = list1[j]\n",
    "        \n",
    "       \n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        if n<=1:\n",
    "            return nums\n",
    "        k %= n\n",
    "        if k==0:\n",
    "            return nums\n",
    "        lo, hi = 0, n-1\n",
    "        while lo < hi:\n",
    "            nums[lo],nums[hi]=nums[hi],nums[lo]\n",
    "            lo+=1\n",
    "            hi-=1\n",
    "        lo, hi = 0, k-1\n",
    "        while lo < hi:\n",
    "            nums[lo],nums[hi]=nums[hi],nums[lo]\n",
    "            lo+=1\n",
    "            hi-=1\n",
    "        lo, hi = k, n - 1\n",
    "        while lo < hi:\n",
    "            nums[lo],nums[hi]=nums[hi],nums[lo]\n",
    "            lo+=1\n",
    "            hi-=1\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums) \n",
    "        if n <= 1:\n",
    "            nums = nums\n",
    "        else:\n",
    "            k %= n\n",
    "        \n",
    "            nums[n:] = nums\n",
    "            del nums[n*2-k:]\n",
    "            del nums[0:n-k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(k%len(nums)):\n",
    "            nums.insert(0,nums.pop())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(k):\n",
    "            last = nums.pop(-1)\n",
    "            nums.insert(0, last)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if n == 1 or k == 0:\n",
    "            return\n",
    "\n",
    "        kms = []\n",
    "        tag = n - k \n",
    "        for i in range(n):\n",
    "            flag = (tag + i) % n\n",
    "            kms.append(nums[flag])\n",
    "        \n",
    "        for i in range(n):\n",
    "            nums[i] = kms[i]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        k%=n\n",
    "        nums[:]=nums[n-k:]+nums[:n-k]  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(k):\n",
    "            nums.insert(0,nums[-1])\n",
    "            del nums[-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        k = k % len(nums)    # 处理长度大于数组长度的情况\n",
    "        nums[:] = nums[-k:] + nums[:-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        k %= len(nums)\n",
    "        nums[:] = nums[-k:] + nums[:-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, nums: List[int], k: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums1 = nums.copy()\n",
    "        for i in range(len(nums)):\n",
    "            j = (i+k)%len(nums)\n",
    "            nums[j] = nums1[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # https://leetcode.cn/problems/rotate-function/description/comments/1521151\n",
    "    # 向右旋转一次：当前结果+sum(nums) - n*当前最后一位\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n = nums.__len__()\n",
    "        if n <= 1:\n",
    "            return 0\n",
    "        sm, f = 0, [0]*n\n",
    "        for i in range(n):\n",
    "            sm += nums[i]\n",
    "            f[0] += i*nums[i]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            f[i] = f[i-1] + sm - n*nums[n-i]\n",
    "        return max(f) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        left, right = 0, n-1\n",
    "        lower, upper = 0, n-1\n",
    "\n",
    "        while left < right and lower < upper:\n",
    "            for i in range(0, right-left):\n",
    "                # (lower, i)->(i, right)->(upper, left+i)->(upper-i, left)->(lower, i)\n",
    "                tmp = [matrix[lower][left+i], matrix[lower+i][right], matrix[upper][right-i], matrix[upper-i][left]]\n",
    "                matrix[lower][left+i] = tmp[3]\n",
    "                matrix[lower+i][right] = tmp[0]\n",
    "                matrix[upper][right-i] = tmp[1]\n",
    "                matrix[upper-i][left] = tmp[2]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "            upper -= 1\n",
    "            lower += 1\n",
    "        return\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: void Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        l = len(matrix)\n",
    "        matrix[:] = [[matrix[l-i-1][j] for i in range(l)] for j in range(l)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix):\n",
    "        n = len(matrix)\n",
    "\n",
    "        matrix.reverse()\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                matrix[i][j], matrix[j][i] = matrix[j][i],matrix[i][j]\n",
    "\n",
    "        \n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: void Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        y = len(matrix)\n",
    "        x = len(matrix[0])\n",
    "        for i in range(round((y+0.2)/2)):\n",
    "            for j in range(round((x-0.2)/2)):\n",
    "                print(i,j)\n",
    "                temp = matrix[i][j]\n",
    "                matrix[i][j] = matrix[y-1-j][i]\n",
    "                matrix[y-1-j][i] = matrix[y-1-i][x-1-j]\n",
    "                matrix[y-1-i][x-1-j] = matrix[j][x-1-i]\n",
    "                matrix[j][x-1-i] = temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: void Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        if len(matrix) == 0:\n",
    "            return\n",
    "        for i in range(len(matrix) // 2):\n",
    "            l = len(matrix) - i * 2 - 1\n",
    "            for j in range(i, i + l):\n",
    "                matrix[i][j], matrix[j][i + l], matrix[i + l][i + l - j + i], matrix[i + l - j + i][i] = matrix[i + l - j + i][i], matrix[i][j], matrix[j][i + l], matrix[i + l][i + l - j + i]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(1, len(matrix[0]) - i):\n",
    "                matrix[i][-j], matrix[-j][i] = matrix[-j][i], matrix[i][-j]\n",
    "        for k in range(len(matrix)):\n",
    "            matrix[k].reverse()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # @param matrix, a list of lists of integers\n",
    "    # @return a list of lists of integers\n",
    "    def rotate(self, matrix):\n",
    "        n = len(matrix)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]\n",
    "        for i in range(n):\n",
    "            matrix[i].reverse()\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: void Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        # 正矩阵的维度\n",
    "        rank = len(matrix[0])\n",
    "        # 第一行，最左边的列，最后一行，最右边一列\n",
    "        rowtop, coleft, rowbot, colright = 0, 0, rank-1, rank-1\n",
    "        while rank > 1:\n",
    "            for i in range(rank-1):\n",
    "                # 第rowtop行的第coleft+i个元素保存\n",
    "                temp = matrix[rowtop][coleft+i]\n",
    "                # 将矩阵第一列的元素给矩阵第一行的元素\n",
    "                matrix[rowtop][coleft+i] = matrix[rowbot-i][coleft]\n",
    "                # 将矩阵最后一行的元素给矩阵第一列的元素\n",
    "                matrix[rowbot-i][coleft] = matrix[rowbot][colright-i]\n",
    "                # 将矩阵最后一列的元素给矩阵最后一行的元素\n",
    "                matrix[rowbot][colright-i] = matrix[rowtop+i][colright]\n",
    "                # 将矩阵第一行的元素给矩阵最后一列的元素\n",
    "                matrix[rowtop+i][colright] = temp\n",
    "            # 矩阵的行数（行列的个数相等，也可以表示为列数）减少2（上下各减少一行）\n",
    "            rank -= 2\n",
    "            # 最高的行数加一，表示行向内进一层，行数减少一行\n",
    "            rowtop += 1\n",
    "            # 最左边的列加一，表示向右进一层，列数减少一列\n",
    "            coleft += 1\n",
    "            # 最下边的行减一，表示向上进程一层，行数减少一行\n",
    "            rowbot -= 1\n",
    "            # 最右边的列减少一列，表示向左进一层，列数减少一列\n",
    "            colright -= 1\n",
    "        return\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: void Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        rank = len(matrix[0])\n",
    "        rowtop, coleft, rowbot, colright = 0, 0, rank-1, rank-1\n",
    "        while rank > 1:\n",
    "            for i in range(rank-1):\n",
    "                temp = matrix[rowtop][coleft+i]\n",
    "                matrix[rowtop][coleft+i] = matrix[rowbot-i][coleft]\n",
    "                matrix[rowbot-i][coleft] = matrix[rowbot][colright-i]\n",
    "                matrix[rowbot][colright-i] = matrix[rowtop+i][colright]\n",
    "                matrix[rowtop+i][colright] = temp\n",
    "            rank -= 2\n",
    "            rowtop += 1\n",
    "            coleft += 1\n",
    "            rowbot -= 1\n",
    "            colright -= 1\n",
    "        return\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def rotate(matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: void Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        import math\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        for i in range(math.ceil(row/2)):\n",
    "            for j in range(i,col-i-1):\n",
    "                row_r_ago=i\n",
    "                col_r_ago=j\n",
    "                row_r = col_r_ago\n",
    "                col_r = col - row_r_ago - 1\n",
    "                temp_ago = matrix[row_r_ago][col_r_ago]\n",
    "                temp=matrix[row_r][col_r]\n",
    "                matrix[row_r][col_r] =temp_ago\n",
    "\n",
    "                row_r_ago = row_r\n",
    "                col_r_ago = col_r\n",
    "                while True:\n",
    "                    row_r = col_r_ago\n",
    "                    col_r = col - row_r_ago - 1\n",
    "                    temp_ago = matrix[row_r][col_r]\n",
    "                    matrix[row_r][col_r] = temp\n",
    "                    temp = temp_ago\n",
    "                    row_r_ago = row_r\n",
    "                    col_r_ago = col_r\n",
    "                    if row_r_ago==i:\n",
    "                        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: void Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        matrix.reverse()\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(i):\n",
    "                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        if not n:\n",
    "            return matrix\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]\n",
    "        \n",
    "        for i in range(n):\n",
    "            matrix[i] = matrix[i][::-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        times = n // 2\n",
    "        for t in range(times):\n",
    "            a = n - t * 2 - 1\n",
    "            for j in range(t, n - t - 1):\n",
    "                temp_1 = matrix[j][n - 1 - t]\n",
    "                matrix[j][n - 1 - t] = matrix[t][j]\n",
    "\n",
    "                temp_2 = matrix[n - 1 - t][n - 1 - j]\n",
    "                matrix[n - 1 - t][n - 1 - j] = temp_1\n",
    "\n",
    "                temp_3 = matrix[n - 1 - j][t]\n",
    "                matrix[n - 1 - j][t] = temp_2\n",
    "\n",
    "                matrix[t][j] = temp_3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        matrix.reverse()\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(i, len(matrix[i])):\n",
    "                tmp = matrix[i][j]\n",
    "                matrix[i][j] = matrix[j][i]\n",
    "                matrix[j][i] = tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        # 先转置，，在每行逆序\n",
    "        n = len(matrix)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]\n",
    "        # print(matrix)\n",
    "        for i in range(n):\n",
    "            for j in range(n // 2):\n",
    "                matrix[i][j], matrix[i][n - j - 1] = matrix[i][n - j - 1], matrix[i][j]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        row, col = len(matrix), len(matrix[0])\n",
    "        lis = []\n",
    "        for i in range(col):\n",
    "            for j in range(row):\n",
    "                lis.append(matrix[j][i])\n",
    "        for i in range(row):\n",
    "            tmp = []\n",
    "            for j in range(col):\n",
    "                tmp.append(lis[i*row + j])\n",
    "            matrix[i][:] = tmp[::-1] \n",
    "\n",
    "# 作者：lilychao\n",
    "# 链接：https://leetcode-cn.com/problems/rotate-image/solution/10xing-dai-ma-ni-zhi-de-yong-you-by-lilychao/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        n = len(matrix)\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "               matrix[j][i], matrix[i][j] = matrix[i][j], matrix[j][i]\n",
    "               \n",
    "        for i in range(n):\n",
    "            matrix[i].reverse()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]\n",
    "        \n",
    "        for item in matrix:\n",
    "            item.reverse()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(i,len(matrix)):\n",
    "                t=matrix[i][j]\n",
    "                matrix[i][j]=matrix[j][i]\n",
    "                matrix[j][i]=t\n",
    "        for h in range(len(matrix)):\n",
    "            for l in range(len(matrix)//2):\n",
    "                t=matrix[h][l]\n",
    "                matrix[h][l]=matrix[h][-l-1]\n",
    "                matrix[h][-l-1]=t\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution0:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        N = len(matrix)\n",
    "        tmpmatrix = copy.deepcopy(matrix)\n",
    "        for line in range(N):\n",
    "            for j in range(N):\n",
    "                matrix[line][N - 1 - j] = tmpmatrix[j][line]\n",
    "        print(matrix)\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        N = len(matrix)\n",
    "        layer = 0\n",
    "        i, j = 0, 0\n",
    "        #print(matrix[1][0])\n",
    "        while layer < math.ceil(N / 2):\n",
    "            cyclenums = N - layer * 2\n",
    "            if cyclenums == 1:\n",
    "                break\n",
    "            \n",
    "            i = layer\n",
    "            j = layer\n",
    "            print(layer, cyclenums, i, j)\n",
    "            for k in range(cyclenums - 1):\n",
    "                numcache = matrix[i][j + k]\n",
    "                matrix[i][j + k] = matrix[i + cyclenums - 1 - k][j]\n",
    "                matrix[i + cyclenums - 1 - k][j] = matrix[i + cyclenums -1][j + cyclenums - 1 -k]\n",
    "                matrix[i + cyclenums -1][j + cyclenums - 1 -k] = matrix[i + k][j + cyclenums -1]\n",
    "                matrix[i + k][j + cyclenums -1] = numcache\n",
    "                print(i,j,k,matrix)\n",
    "            layer += 1    \n",
    "'''\n",
    "            corner4 = [i + cyclenums - 1, j]\n",
    "            corner3 = [i + cyclenums - 1, j + cyclenums - 1]\n",
    "            corner2 = [i, j + cyclenums -1]\n",
    "            numcache = matrix[i][j]\n",
    "            matrix[i][j] = matrix[corner4[0]][corner4[1]]\n",
    "            matrix[corner4[0]][corner4[1]] = matrix[corner3[0]][corner3[1]]\n",
    "            matrix[corner3[0]][corner3[1]] = matrix[corner2[0]][corner2[1]]\n",
    "            matrix[corner2[0]][corner2[1]] = numcache\n",
    "            print(matrix)\n",
    "            #cyclenums = cyclenums - 2\n",
    "            if cyclenums == 0:\n",
    "                break\n",
    "            numcache = matrix[i][j + 1 : N - 1 - j].copy()\n",
    "            print(numcache)\n",
    "            for k in range(len(numcache)):\n",
    "                print(matrix[1][0])\n",
    "                print(matrix[i + cyclenums - 2 - k][j])\n",
    "                matrix[i][j + 1 + k] = matrix[i + cyclenums - 2 - k][j]\n",
    "                matrix[i + 1 + k][j] = matrix[i + cyclenums - 1][j + 1 + k]\n",
    "                matrix[i + cyclenums - 1][j + 1 + k] = matrix[i + cyclenums - 2 - k][j + cyclenums -1]\n",
    "                matrix[i + 1 + k][j + cyclenums - 1] = numcache[k]\n",
    "                print(i, j, k, matrix)\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        list1=[]\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[i])):\n",
    "                list1.append(matrix[i][j])\n",
    "        count=0\n",
    "        for j in range(len(list1)):\n",
    "            \n",
    "            for  i in range(len(matrix)):\n",
    "                if (j % len(matrix[i]))==i:\n",
    "                    print(list1[j],i)\n",
    "                    matrix[i][len(matrix)-1-count]=list1[j]\n",
    "                    if j%len(matrix)==len(matrix)-1:\n",
    "                        count+=1\n",
    "                    \n",
    "                    break\n",
    "            \n",
    "         \n",
    "    \n",
    "                        \n",
    "                        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        size = len(matrix)\n",
    "        count = 0\n",
    "        while size - 2 * count > 1:\n",
    "            s = count\n",
    "            e = size - count -1\n",
    "            for i in range(s, e):\n",
    "                p1 = (s, i)\n",
    "                p2 = (i, e)\n",
    "                p3 = (e, e + s - i)\n",
    "                p4 = (e + s - i, s)\n",
    "                r, c = p4\n",
    "                temp = matrix[r][c]\n",
    "                for n in [p1, p2, p3, p4]:\n",
    "                    r, c = n\n",
    "                    print(s, e, r, c)\n",
    "                    temp1 = matrix[r][c]\n",
    "                    matrix[r][c] = temp\n",
    "                    temp = temp1\n",
    "            count += 1\n",
    "            # [[5,1,9,11],\n",
    "            #  [2,4,8,10],\n",
    "            #  [13,3,6,7],\n",
    "            #  [15,14,12,16]]\n",
    "            # [[15,13,2,5],\n",
    "            #  [14,3,4,1],\n",
    "            #  [12,8,6,9],\n",
    "            #  [16,7,10,11]]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        for i in range(n//2):\n",
    "            for j in range(i,n-1-i):\n",
    "                temp = matrix[i][j]\n",
    "                matrix[i][j] = matrix[n-1-j][i]\n",
    "                matrix[n-1-j][i] = matrix[n-1-i][n-1-j]\n",
    "                matrix[n-1-i][n-1-j] = matrix[j][n-1-i]\n",
    "                matrix[j][n-1-i]=temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        n = len(matrix)\n",
    "        # 水平翻转\n",
    "        for i in range(n // 2):\n",
    "            for j in range(n):\n",
    "                matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]\n",
    "        # 主对角线翻转\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        for i in range(n //2):\n",
    "            tmp = matrix[i]\n",
    "            matrix[i] = matrix[n-1-i]\n",
    "            matrix[n-1-i] = tmp\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                tmp = matrix[i][j]\n",
    "                matrix[i][j] = matrix[j][i]\n",
    "                matrix[j][i] = tmp\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        for i in range(n//2):\n",
    "            for j in range(n):\n",
    "                matrix[i][j] ,matrix[n-i-1][j] = matrix[n-i-1][j],matrix[i][j]\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\r\n",
    "        \"\"\"\r\n",
    "        Do not return anything, modify matrix in-place instead.\r\n",
    "        \"\"\"\r\n",
    "        matrix[:] =  zip(*matrix)\r\n",
    "        for i in range(len(matrix)):\r\n",
    "            matrix[i] = matrix[i][::-1]\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        if matrix is None or len(matrix) <= 1 or len(matrix[0]) <= 1:\n",
    "            return matrix\n",
    "        \n",
    "        size = len(matrix)\n",
    "        for i in range(int((size+1)/2)):\n",
    "            for j in range(int((size+1)/2)):\n",
    "                if size%2==1 and (j==int(size/2)):\n",
    "                    continue\n",
    "                print(\"index\", i, j)\n",
    "                if i == j:\n",
    "                    matrix[i][j], matrix[i][size-1-j], matrix[size-1-i][size-1-j], matrix[size-1-i][j] = matrix[size-1-i][j], matrix[i][j], matrix[i][size-1-j], matrix[size-1-i][size-1-j]\n",
    "                else:\n",
    "                    print(matrix[i][j], matrix[j][size-1-i], matrix[size-1-i][size-1-j], matrix[size-1-j][i])\n",
    "                    print(matrix[size-1-j][i], matrix[i][j], matrix[j][size-1-i], matrix[size-1-i][size-1-j])\n",
    "                    matrix[i][j], matrix[j][size-1-i], matrix[size-1-i][size-1-j], matrix[size-1-j][i] = matrix[size-1-j][i], matrix[i][j], matrix[j][size-1-i], matrix[size-1-i][size-1-j]\n",
    "\n",
    "        return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]\n",
    "        for row in matrix:\n",
    "            row.reverse()\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "\n",
    "        for i in range(n//2):\n",
    "            for j in range(n):\n",
    "                matrix[i][j] ,matrix[n -i -1][j] = matrix[n -i -1][j] , matrix[i][j]\n",
    "            \n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                matrix[i][j] , matrix[j][i] = matrix[j][i],matrix[i][j]\n",
    "\n",
    "\n",
    "        # n = len(matrix)\n",
    "        # for i in range(n //2 ):\n",
    "        #     for j in range((n+1)//2):\n",
    "        #         matrix[i][j], matrix[n - j - 1][i], matrix[n - i - 1][n - j - 1], matrix[j][n - i - 1] \\\n",
    "        #             = matrix[n - j - 1][i], matrix[n - i - 1][n - j - 1], matrix[j][n - i - 1], matrix[i][j]\n",
    "\n",
    "\n",
    "        # # n = len(matrix)\n",
    "        # # matrix_new = [[0]*n for _ in range(n)]\n",
    "        # # for i in range(n):\n",
    "        # #     for j in range(n):\n",
    "        # #         matrix_new[j][n - i - 1] = matrix[i][j]\n",
    "        \n",
    "        # # matrix[:] = matrix_new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        for i in range(1,len(matrix)//2+1):\n",
    "            for j in range(1,(len(matrix)//2+int(len(matrix)%2!=0))+1):\n",
    "                matrix[i-1][j-1],matrix[j-1][len(matrix)-i],matrix[len(matrix)-i][len(matrix)-j],matrix[len(matrix)-j][i-1]=matrix[len(matrix)-j][i-1],matrix[i-1][j-1],matrix[j-1][len(matrix)-i],matrix[len(matrix)-i][len(matrix)-j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return None\n",
    "\n",
    "        length = 1\n",
    "        cur = head\n",
    "\n",
    "        while cur.next:\n",
    "            length += 1\n",
    "            cur = cur.next\n",
    "        \n",
    "        k = k % length\n",
    "        cur.next = head\n",
    "\n",
    "        temp = head\n",
    "        for i in range(length - k - 1):\n",
    "            temp = temp.next\n",
    "        \n",
    "        new_head = temp.next\n",
    "        temp.next = None\n",
    "\n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head, k):\n",
    "        if head == None or head.next == None or k==0:\n",
    "            return head\n",
    "        count = 0\n",
    "        extra = ListNode(0)\n",
    "        extra.next = head\n",
    "        p = extra\n",
    "        while (p.next):\n",
    "            count+=1\n",
    "            p = p.next\n",
    "        if k % count ==0:\n",
    "            return head\n",
    "        step = count - k % count\n",
    "        p.next = extra.next\n",
    "        while (step>0):\n",
    "            p = p.next\n",
    "            step-=1\n",
    "        extra.next = p.next\n",
    "        p.next = None\n",
    "        return extra.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head, k):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type k: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if head == None or head.next == None:\n",
    "            return head\n",
    "        p = head\n",
    "        q = None\n",
    "        count = 0\n",
    "        while p != None:\n",
    "            q = p\n",
    "            p = p.next\n",
    "            count += 1\n",
    "        \n",
    "        c = (count - k % count) % count\n",
    "        if c == 0:\n",
    "            return head\n",
    "        q.next = head\n",
    "        p = head\n",
    "        for i in range(c):\n",
    "            q = p\n",
    "            p = p.next\n",
    "        q.next = None\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head, k):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type k: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if head == None:\n",
    "            return head\n",
    "        \n",
    "        p = head\n",
    "        l = 0\n",
    "        tail = None\n",
    "        while p != None:\n",
    "            l += 1\n",
    "            tail = p\n",
    "            p = p.next\n",
    "\n",
    "        k = k % l\n",
    "\n",
    "        if k == 0:\n",
    "            return head \n",
    "        \n",
    "        p = head\n",
    "        print(l, k)\n",
    "        while l > k + 1:\n",
    "            p = p.next\n",
    "            l -= 1\n",
    "\n",
    "        new_head = p.next\n",
    "        p.next = None\n",
    "        tail.next = head\n",
    "\n",
    "        return new_head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head, k):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type k: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return head\n",
    "        l = 1\n",
    "        cur = head\n",
    "        while cur and cur.next:\n",
    "            l += 1\n",
    "            cur = cur.next\n",
    "        tail = cur\n",
    "        k = l - k % l\n",
    "        for i in range(k):\n",
    "            tail.next = head\n",
    "            head = head.next\n",
    "            tail = tail.next\n",
    "            tail.next = None\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        temp=head\n",
    "        leng=1\n",
    "        if head==None:\n",
    "            return []\n",
    "        while head.next!=None:\n",
    "            head=head.next\n",
    "            leng+=1\n",
    "        step=k%leng\n",
    "        if step ==0:\n",
    "            return temp\n",
    "        temp2=temp\n",
    "        for i in range(leng-step-1):\n",
    "            temp2=temp2.next\n",
    "        result=temp2.next\n",
    "        temp2.next=None\n",
    "        head.next=temp\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: 'ListNode', k: 'int') -> 'ListNode':\n",
    "        if k == 0 or head is None:\n",
    "            return head\n",
    "        first = ListNode(0)\n",
    "        first.next = head\n",
    "        count = 0\n",
    "        cur = first\n",
    "        while cur.next:\n",
    "            count += 1\n",
    "            cur = cur.next\n",
    "        cur.next = head\n",
    "        num = count - (k % count)\n",
    "        res = first\n",
    "        while num>0:\n",
    "            res = res.next\n",
    "            num -= 1\n",
    "        first.next = res.next\n",
    "        res.next = None\n",
    "        return first.next\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        if not head.next:\n",
    "            return head\n",
    "        \n",
    "        old_tail = head\n",
    "        n = 1\n",
    "        while old_tail.next:\n",
    "            old_tail = old_tail.next\n",
    "            n += 1\n",
    "        old_tail.next = head\n",
    "        new_tail = head\n",
    "        for i in range(n - k % n - 1):\n",
    "            new_tail = new_tail.next\n",
    "        new_head = new_tail.next\n",
    "        new_tail.next = None\n",
    "        \n",
    "        return new_head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        if not head: return head\n",
    "        \n",
    "        node, list_len = head, 0\n",
    "        \n",
    "        while node:\n",
    "            node = node.next\n",
    "            list_len += 1\n",
    "\n",
    "        node, idx = head, 0\n",
    "        k %= list_len\n",
    "        \n",
    "        if k == 0: return head\n",
    "        \n",
    "        while True:\n",
    "            if idx == list_len - k - 1:\n",
    "                ans = node.next\n",
    "                node.next = None\n",
    "                node = ans\n",
    "            elif idx == list_len - 1:\n",
    "                node.next = head\n",
    "                break\n",
    "            else: node = node.next\n",
    "            idx += 1\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        o_head,cnt = head,1\n",
    "        while head.next:\n",
    "            head,cnt = head.next,cnt+1\n",
    "        head.next = o_head\n",
    "\n",
    "        step = cnt - k%cnt-1\n",
    "        while step > 0:\n",
    "            o_head,step = o_head.next,step-1\n",
    "        \n",
    "        new_head,o_head.next = o_head.next,None\n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head, k):\n",
    "        if not head:\n",
    "            return None\n",
    "        if not head.next:\n",
    "            return head\n",
    "\n",
    "        len = 0\n",
    "        l = head\n",
    "        while l.next!= None:\n",
    "            len += 1\n",
    "            l = l.next\n",
    "        l.next = head\n",
    "        len+=1\n",
    "        ptr = head\n",
    "        for i in range(0,len-k%len-1):\n",
    "            ptr = ptr.next\n",
    "        head = ptr.next\n",
    "        ptr.next = None\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        \n",
    "        old_tail, n = head, 1\n",
    "        while old_tail.next:\n",
    "            old_tail = old_tail.next\n",
    "            n += 1\n",
    "        # 成环\n",
    "        old_tail.next = head\n",
    "        # 寻找新的链表结尾\n",
    "        new_tail, new_head = None, head\n",
    "        for _ in range(n - k % n):\n",
    "            new_tail = new_head\n",
    "            new_head = new_head.next\n",
    "        # 断开链接\n",
    "        new_tail.next = None\n",
    "        return new_head\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    # def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "    #     if not head:\n",
    "    #         return None\n",
    "    #     if not head.next:\n",
    "    #         return head\n",
    "    #     n = 1\n",
    "    #     old_tail = head\n",
    "    #     while old_tail.next:\n",
    "    #         old_tail = old_tail.next\n",
    "    #         n += 1\n",
    "    #     # cycle\n",
    "    #     old_tail.next = head\n",
    "    #     # find the new head\n",
    "    #     new_tail = head\n",
    "    #     for i in range(n - k % n - 1):\n",
    "    #         new_tail = new_tail.next\n",
    "    #     head = new_tail.next\n",
    "    #     new_tail.next = None\n",
    "\n",
    "    #     return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head \n",
    "        old_tail = head \n",
    "        n = 1\n",
    "        while old_tail.next:\n",
    "            old_tail = old_tail.next \n",
    "            n += 1\n",
    "        old_tail.next = head \n",
    "        for _ in range(n - k % n - 1):\n",
    "            head = head.next \n",
    "        newHead = head.next \n",
    "        head.next = None \n",
    "        return newHead\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        # base cases\n",
    "        if not head:\n",
    "            return None\n",
    "        if not head.next:\n",
    "            return head\n",
    "        \n",
    "        # close the linked list into the ring\n",
    "        old_tail = head\n",
    "        n = 1\n",
    "        while old_tail.next:\n",
    "            old_tail = old_tail.next\n",
    "            n += 1\n",
    "        old_tail.next = head\n",
    "        \n",
    "        # find new tail : (n - k % n - 1)th node\n",
    "        # and new head : (n - k % n)th node\n",
    "        new_tail = head\n",
    "        for i in range(n - k % n - 1):\n",
    "            new_tail = new_tail.next\n",
    "        new_head = new_tail.next\n",
    "        \n",
    "        # break the ring\n",
    "        new_tail.next = None\n",
    "        \n",
    "        return new_head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "class Solution:\r\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\r\n",
    "        if not head or not head.next:\r\n",
    "            return head\r\n",
    "        oldTail = head\r\n",
    "        n = 1\r\n",
    "        # oldTail 指针到最后一个元素/\r\n",
    "        while oldTail.next:\r\n",
    "            oldTail = oldTail.next\r\n",
    "            n += 1\r\n",
    "        # 将旧链表连接成环：\r\n",
    "        oldTail.next = head\r\n",
    "        newTail = head\r\n",
    "        # n - k%n - 1 环形新链表头节点的前一个节点\r\n",
    "        for _ in range(n - k%n - 1):\r\n",
    "            newTail = newTail.next\r\n",
    "        # 新链表的头节点\r\n",
    "        newHead = newTail.next\r\n",
    "        # 将新链表的头尾断开：\r\n",
    "        newTail.next = None\r\n",
    "        return newHead\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        if head is None: return head\n",
    "        # 计算长度\n",
    "        length = 0\n",
    "        cur = head\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            length += 1\n",
    "\n",
    "        if k % length == 0: # 若不移动直接返回\n",
    "            return head\n",
    "        \n",
    "        # 取出旋转链表\n",
    "        length -= k % length\n",
    "        cur = head\n",
    "        while length > 1:\n",
    "            print ('cur loop:  ',cur)\n",
    "            cur = cur.next\n",
    "            length -= 1\n",
    "        \n",
    "        tmp = cur.next\n",
    "        print ('tmp:',tmp)\n",
    "        cur.next = None # head去尾\n",
    "        \n",
    "        # 移动到链表尾部\n",
    "        cur1 = tmp\n",
    "        while cur1 and cur1.next:\n",
    "            cur1 = cur1.next\n",
    "        cur1.next = head\n",
    "\n",
    "        return tmp\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "from multiprocessing import dummy\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        return self.rotate_right(head, k)\n",
    "\n",
    "    def rotate_right(self, head: ListNode, k: int) -> ListNode:\n",
    "        if not head or k <= 0:\n",
    "            return head\n",
    "\n",
    "        def cut(cur: ListNode, k: int) -> ListNode:\n",
    "            while k > 1 and cur.next:\n",
    "                cur = cur.next\n",
    "                k -= 1\n",
    "            next_head = cur.next\n",
    "            cur.next = None\n",
    "            return next_head\n",
    "\n",
    "        length = 0\n",
    "        p = head\n",
    "        while p:\n",
    "            p = p.next\n",
    "            length += 1\n",
    "        k = k % length\n",
    "\n",
    "        if k == 0:\n",
    "            return head\n",
    "\n",
    "        second_head = cut(head, length - k)\n",
    "        tail = second_head\n",
    "        while tail.next:\n",
    "            tail = tail.next\n",
    "        tail.next = head\n",
    "        return second_head\n",
    "\n",
    "\n",
    "    def rotate_right_one(self, head: ListNode, k: int) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        length = 0\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        pre = dummy\n",
    "        fast = dummy.next\n",
    "        tail = dummy\n",
    "        slow = dummy.next\n",
    "        p = dummy\n",
    "        while p.next:\n",
    "            p = p.next\n",
    "            length += 1\n",
    "\n",
    "        k = k % length\n",
    "        counter = 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: ListNode, k: int) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        \n",
    "        pre = mid = cur = head\n",
    "        size = 0\n",
    "        while cur!=None:\n",
    "            size+=1\n",
    "            cur = cur.next\n",
    "        k = k%size\n",
    "        step = k\n",
    "        cur = head\n",
    "        while cur.next!=None:\n",
    "            cur = cur.next\n",
    "            step-=1\n",
    "            if not step:\n",
    "                if pre != mid:\n",
    "                    pre = mid\n",
    "                mid = cur\n",
    "                step = k\n",
    "            print(pre.val, mid.val, cur.val,step)\n",
    "        step = k-step\n",
    "        while step:\n",
    "            pre = pre.next\n",
    "            step-=1\n",
    "        \n",
    "        cur.next = head\n",
    "        head = pre.next\n",
    "        pre.next = None\n",
    "        return head\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        cur_head = head\n",
    "        nodes = []\n",
    "        while cur_head:\n",
    "            nodes.append(cur_head)\n",
    "            cur_head = cur_head.next\n",
    "        if not nodes:\n",
    "            return head\n",
    "        head_idx = (len(nodes) - k % len(nodes)) % len(nodes)\n",
    "        # for node in nodes:\n",
    "        #     print(node)\n",
    "        pre_idx = (head_idx - 1 + len(nodes)) % len(nodes) \n",
    "        tail = nodes[-1]\n",
    "        tail.next = head\n",
    "        nodes[pre_idx].next = None\n",
    "        return nodes[head_idx]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        if k==0 or not head or not head.next:\n",
    "            return head\n",
    "        n = 1\n",
    "        cur = head\n",
    "        while cur.next:\n",
    "            cur = cur.next\n",
    "            n += 1\n",
    "        \n",
    "        if (add := n - k % n) == n:\n",
    "            return head\n",
    "        \n",
    "        cur.next = head\n",
    "        while add:\n",
    "            cur = cur.next\n",
    "            add -= 1\n",
    "        \n",
    "        ret = cur.next\n",
    "        cur.next = None\n",
    "        return ret\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        if head == None:\n",
    "            return None\n",
    "        length = 0\n",
    "        temp = head\n",
    "        while temp:\n",
    "            length += 1\n",
    "            temp = temp.next\n",
    "        \n",
    "        k %= length\n",
    "        if k == 0:\n",
    "            return head\n",
    "        \n",
    "        left = right = head\n",
    "        for i in range(k):\n",
    "            right = right.next\n",
    "        \n",
    "        while right.next:\n",
    "            left = left.next\n",
    "            right = right.next\n",
    "        \n",
    "        right.next = head\n",
    "        head = left.next\n",
    "        left.next = None\n",
    "\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        if k == 0 or not head or not head.next:\n",
    "            return head\n",
    "        \n",
    "        cur = head\n",
    "        n = 1\n",
    "        while cur.next:\n",
    "            cur = cur.next\n",
    "            n += 1\n",
    "\n",
    "        add = n - k % n\n",
    "        if add == n:\n",
    "            return head\n",
    "\n",
    "        cur.next = head\n",
    "        while add:\n",
    "            cur = cur.next\n",
    "            add -= 1\n",
    "        \n",
    "        ret = cur.next\n",
    "        cur.next = None\n",
    "        return ret\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        if not head: return head\n",
    "        nodecount = 0\n",
    "        # 计算节点个数\n",
    "        cur = head\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            nodecount += 1\n",
    "        # rotatenode : 从右拿几个放在左边\n",
    "        rotatenode = k % nodecount\n",
    "        if rotatenode == 0: return head\n",
    "        tmp = head\n",
    "        right = rightpiece = ListNode()\n",
    "        left = leftpiece = ListNode()\n",
    "        i = 0\n",
    "        while tmp:\n",
    "            i += 1\n",
    "            # 右片前 n - 1个节点\n",
    "            if i < nodecount - rotatenode:\n",
    "                rightpiece.val = tmp.val\n",
    "                rightpiece.next = ListNode()\n",
    "                rightpiece = rightpiece.next\n",
    "                tmp = tmp.next\n",
    "            # 右片最后一个节点\n",
    "            elif i == nodecount - rotatenode:\n",
    "                rightpiece.val = tmp.val\n",
    "                tmp = tmp.next\n",
    "            # 左片前 n - 1个节点\n",
    "            elif i > nodecount - rotatenode and i < nodecount:\n",
    "                leftpiece.val = tmp.val\n",
    "                leftpiece.next = ListNode()\n",
    "                leftpiece = leftpiece.next\n",
    "                tmp = tmp.next\n",
    "            # 左片最后一个节点\n",
    "            else:\n",
    "                leftpiece.val = tmp.val\n",
    "                leftpiece.next = right\n",
    "                tmp = tmp.next\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: list, k: int):\n",
    "        if k ==0 or not head or not head.next:\n",
    "            return head\n",
    "        # print(type(head), head)\n",
    "        org_head = copy.deepcopy(head)\n",
    "        data = []\n",
    "        while head.next:\n",
    "                data.append(head.val)\n",
    "                head = head.next\n",
    "        data.append(head.val)\n",
    "        print(data)\n",
    "        data_length = len(data)\n",
    "        transfer = k%data_length\n",
    "        if transfer == 0:\n",
    "            return org_head\n",
    "        # print('transfer', transfer)\n",
    "        new_data = data[-transfer:] + data[:data_length-transfer]\n",
    "        new_data.reverse()\n",
    "        # print('new_data', new_data)\n",
    "\n",
    "        new_head = ListNode(val=new_data[0])\n",
    "\n",
    "        for n in new_data[1:]:\n",
    "            tmp_node = ListNode(val=n)\n",
    "            tmp_node.next = new_head\n",
    "            new_head = tmp_node\n",
    "        # print(type(new_head), new_head)\n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        x=head\n",
    "        count=0\n",
    "        tail=x\n",
    "        while x:\n",
    "            count+=1\n",
    "            tail=x\n",
    "            x=x.next\n",
    "        if count==0: return head\n",
    "        #print('tail=',tail.val)\n",
    "        #print(count)\n",
    "        k=k%count\n",
    "        if k==0 : return head\n",
    "        x=head\n",
    "        last=head\n",
    "        #print(count,k,count-k)\n",
    "        for i in range(count-k):\n",
    "            last=x\n",
    "            x=x.next\n",
    "        #print('head=',head.val)\n",
    "        #print('last=',last.val)\n",
    "\n",
    "        tail.next=head\n",
    "        last.next=None\n",
    "        return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        start = head\n",
    "        end = head\n",
    "        list_len = 0\n",
    "        while end:\n",
    "            end = end.next\n",
    "            list_len += 1\n",
    "        \n",
    "        k = k%list_len\n",
    "        end = head\n",
    "\n",
    "        for i in range(k):\n",
    "            end = end.next\n",
    "        \n",
    "        if not end:\n",
    "            return head\n",
    "        \n",
    "        while end.next:\n",
    "            start = start.next\n",
    "            end = end.next\n",
    "        \n",
    "        end.next = head\n",
    "        new_head = start.next\n",
    "        start.next = None\n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        if not head or not head.next or k == 0:\n",
    "            return head\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        # 计算链表长度n\n",
    "        n = 0\n",
    "        p = head\n",
    "        while p:\n",
    "            p = p.next\n",
    "            n += 1\n",
    "        # 计算实际旋转次数k\n",
    "        k %= n\n",
    "        # 找到链表的倒数第k+1个节点q\n",
    "        p, q = head, head\n",
    "        # p先走k步\n",
    "        for _ in range(k):\n",
    "            p = p.next\n",
    "        # p和q开始同步走，直到p到达最后一个节点\n",
    "        while p and p.next:\n",
    "            p = p.next\n",
    "            q = q.next\n",
    "        # 当前尾节点连到头节点之前\n",
    "        p.next = head\n",
    "        # 倒数第k个节点变成头节点\n",
    "        dummy.next = q.next\n",
    "        # 倒数第k+1个节点变尾节点\n",
    "        q.next = None\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        N = len(matrix)\n",
    "        for i in range(N):\n",
    "            for j in range(i):\n",
    "                matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]\n",
    "\n",
    "        for i in range(N):\n",
    "            matrix[i][:] = matrix[i][::-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n=len(matrix)\n",
    "        \n",
    "        for i in range(n//2):\n",
    "            for j in range(n):\n",
    "                matrix[i][j],matrix[n-1-i][j]=matrix[n-1-i][j],matrix[i][j]\n",
    "        for i in range(n):\n",
    "            for j in range(0,i):\n",
    "                matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "    \n",
    "        \"\"\"\n",
    "        N = len(matrix)\n",
    "        for i in range(N):\n",
    "            for j in range(i, N):\n",
    "                matrix[i][j], matrix[j][i]= matrix[j][i], matrix[i][j]\n",
    "        for i in range(N):\n",
    "            matrix[i][:]=matrix[i][::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        def get_center_sym_4_point(i,j,N):\n",
    "            return (i,j), (j, N-1-i), (N-1-j, i), (N-1-i, N-1-j)\n",
    "\n",
    "        N = len(matrix)\n",
    "        # 遍历矩形的第二象限\n",
    "        s1 = set()\n",
    "        s2 = set()\n",
    "        s3 = set()\n",
    "        s4 = set()\n",
    "\n",
    "        for i in range(N//2):\n",
    "            for j in range((N+1)//2):\n",
    "                (x2,y2), (x1,y1), (x3,y3), (x4,y4) = get_center_sym_4_point(i,j,N)\n",
    "                matrix[x1][y1], matrix[x2][y2], matrix[x3][y3], matrix[x4][y4] = \\\n",
    "                    matrix[x2][y2], matrix[x3][y3], matrix[x4][y4], matrix[x1][y1]\n",
    "        # for i in range(N):\n",
    "        #     for j in range(N):\n",
    "        #         if (i,j) in s1:\n",
    "        #             print(1,end=\"\")\n",
    "        #         elif (i,j) in s2:\n",
    "        #             print(2,end=\"\")\n",
    "        #         elif (i,j) in s3:\n",
    "        #             print(3,end=\"\")\n",
    "        #         elif (i,j) in s4:\n",
    "        #             print(4,end=\"\")\n",
    "        #     print()\n",
    "        return matrix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        m = len(matrix)\n",
    "        # 上下反转\n",
    "        for i in range(m // 2):\n",
    "            for j in range(m):\n",
    "                matrix[i][j],matrix[m-i-1][j] = matrix[m-i-1][j],matrix[i][j]\n",
    "        # 对角线反转\n",
    "        for i in range(m):\n",
    "            for j in range(i):\n",
    "                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]\n",
    "\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]\n",
    "        for i in range(n):\n",
    "            for j in range(n//2):\n",
    "                matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        N = len(matrix)\n",
    "        for i in range(N):\n",
    "            for j in range(i + 1, N):\n",
    "                matrix[j][i], matrix[i][j] = matrix[i][j], matrix[j][i]\n",
    "        for i in range(N):\n",
    "            matrix[i] = matrix[i][::-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        matrix.reverse()\n",
    "        length=len(matrix)\n",
    "        for i in range(length):\n",
    "            for j in range(i,length):\n",
    "                a=matrix[i][j]\n",
    "                matrix[i][j]=matrix[j][i]\n",
    "                matrix[j][i]=a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        # 顺时针旋转90  先对角线翻转，再水平翻转\n",
    "        # 逆时针旋转90  先水平翻转，再对角线翻转\n",
    "\n",
    "        # 对角线翻转\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(i):\n",
    "                matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]\n",
    "        \n",
    "        # 水平翻转\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix)//2):\n",
    "                x=len(matrix)-j-1\n",
    "                matrix[i][j],matrix[i][x] = matrix[i][x],matrix[i][j]\n",
    "        \n",
    "        # return matrix\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        _len = len(matrix)\n",
    "        temp = copy.deepcopy(matrix)\n",
    "        for i in range(_len):\n",
    "            for j in range(_len):\n",
    "\n",
    "                # matrix[j][_len-i-1] =temp[i][j]\n",
    "                # 对角线反转\n",
    "                matrix[i][j] = temp[j][i]\n",
    "        temp2 = copy.deepcopy(matrix)\n",
    "        for i in range(_len):\n",
    "            for j in range(_len):\n",
    "                # 水平中线对折\n",
    "                matrix[i][j] = temp2[i][_len - j - 1]\n",
    "\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n=len(matrix)\n",
    "        mat=[[0 for i in range(n)] for j in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                mat[j][n-i-1]=matrix[i][j]\n",
    "        \n",
    "        matrix[:]=mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        n = len(matrix)\n",
    "        # Python 这里不能 matrix_new = matrix 或 matrix_new = matrix[:] 因为是引用拷贝\n",
    "        matrix_new = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                matrix_new[j][n - i - 1] = matrix[i][j]\n",
    "        # 不能写成 matrix = matrix_new\n",
    "        matrix[:] = matrix_new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        N=len(matrix)\n",
    "        m=[]\n",
    "        for i in range(N):\n",
    "            for j in range(N):\n",
    "                if j<N-i-1:\n",
    "                    temp=matrix[i][j]\n",
    "                    matrix[i][j]=matrix[N-1-j][N-1-i]\n",
    "                    matrix[N-1-j][N-1-i]=temp\n",
    "        for i in range(N):\n",
    "            if i<N-i-1:\n",
    "                m=matrix[i][:]\n",
    "                matrix[i][:]=matrix[N-i-1][:]\n",
    "                matrix[N-i-1][:]=m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        size = len(matrix)\n",
    "        # Horizontal flip\n",
    "        for i in range(size // 2):\n",
    "            matrix[i], matrix[size - i - 1] = matrix[size - i - 1], matrix[i]\n",
    "        # Transpose the matrix\n",
    "        for i in range(size):\n",
    "            for j in range(i):\n",
    "                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        N = len(matrix)\n",
    "        for i in range(N // 2):\n",
    "            for j in range(i, N - i - 1):\n",
    "                temp = matrix[i][j]\n",
    "                matrix[i][j] = matrix[N - 1 - j][i]\n",
    "                matrix[N - 1 - j][i] = matrix[N - 1 - i][N - 1 - j]\n",
    "                matrix[N - 1 - i][N - 1 - j] = matrix[j][N - 1 - i]\n",
    "                matrix[j][N - 1 - i] = temp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        for i in range(0,n):\n",
    "            for j in range(i,n):\n",
    "                # temp = matrix[i][j]\n",
    "                # matrix[i][j] = matrix[j][i]\n",
    "                # matrix[j][i] = temp\n",
    "                matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]\n",
    "        for i in range(n):\n",
    "             for j in range(n//2):\n",
    "                 matrix[i][j],matrix[i][n-1-j] = matrix[i][n-1-j],matrix[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        n = len(matrix)\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]\n",
    "        for i in range(n):\n",
    "            matrix[i].reverse()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        u = n//2\n",
    "        for i in range(u):\n",
    "            for j in range(u):\n",
    "                temp = matrix[i][j]\n",
    "                matrix[i][j] = matrix[n-1-j][i]\n",
    "                matrix[n-1-j][i]=matrix[n-1-i][n-1-j]\n",
    "                matrix[n-1-i][n-1-j]=matrix[j][n-1-i]\n",
    "                matrix[j][n-1-i] = temp\n",
    "        if n%2 == 1:\n",
    "            for i in range(u):\n",
    "                temp = matrix[i][u]\n",
    "                matrix[i][u] = matrix[u][i]\n",
    "                matrix[u][i] = matrix[n-1-i][u]\n",
    "                matrix[n-1-i][u] = matrix[u][n-1-i]\n",
    "                matrix[u][n-1-i] = temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        length=len(matrix)\n",
    "        ls=[[0]*length for _ in range(length)]\n",
    "        for n in range(length):\n",
    "            for m in range(length):\n",
    "                #ls[m][length-n-1]=matrix[n][m]\n",
    "                ls[m][-(n+1)]=matrix[n][m]\n",
    "        matrix[:]=ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix) -> None:\n",
    "        n = len(matrix[0])\n",
    "        j = 0\n",
    "        for i in range(0, n):\n",
    "            matrix[i].reverse()\n",
    "        \n",
    "        i = 0\n",
    "        for i in range(0, n-1):\n",
    "            for j in range(0, n-i):\n",
    "                \n",
    "                temp = matrix[i][j]\n",
    "                matrix[i][j] = matrix[n-j-1][n-i-1]\n",
    "                matrix[n-j-1][n-i-1] = temp\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        matrix_new = copy.deepcopy(matrix)\n",
    "        for x in range(len(matrix)):\n",
    "            for y in range(len(matrix[x])):\n",
    "                matrix[x][y] = matrix_new[len(matrix) - 1 - y][x]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        for i in range(n // 2):\n",
    "            for j in range(n):\n",
    "                matrix[i][j], matrix[n-i-1][j] = matrix[n-i-1][j], matrix[i][j]\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]\n",
    "        return matrix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        # 特判小矩阵\n",
    "        if len(matrix) <= 1:\n",
    "            return matrix\n",
    "\n",
    "        # 标记一圈的起点\n",
    "        strow, stcol = 0, 0\n",
    "        # 记录圈的大小\n",
    "        edgelen = len(matrix) - 1\n",
    "        loopt = len(matrix) // 2\n",
    "        ctr = 0\n",
    "        while ctr < loopt:\n",
    "            inner_ctr = 0\n",
    "            while inner_ctr < edgelen:\n",
    "                r1, c1 = strow, stcol + inner_ctr\n",
    "                r2, c2 = strow + inner_ctr, stcol + edgelen\n",
    "                r3, c3 = strow + edgelen, stcol + edgelen - inner_ctr\n",
    "                r4, c4 = strow + edgelen - inner_ctr, stcol\n",
    "                # print((r1, c1), (r2, c2), (r3, c3), (r4, c4))\n",
    "                matrix[r1][c1], matrix[r2][c2], matrix[r3][c3], matrix[r4][c4] = matrix[r4][c4], matrix[r1][c1], matrix[r2][c2], matrix[r3][c3]\n",
    "                inner_ctr += 1\n",
    "            ctr += 1\n",
    "            strow += 1\n",
    "            stcol += 1\n",
    "            edgelen -= 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        _len = len(matrix)\n",
    "        temp = copy.deepcopy(matrix)\n",
    "        for i in range(_len):\n",
    "            for j in range(_len):\n",
    "                matrix[j][_len-i-1] =temp[i][j]\n",
    "\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        _len = len(matrix)\n",
    "        temp = copy.deepcopy(matrix)\n",
    "        for i in range(_len):\n",
    "            for j in range(_len):\n",
    "                matrix[j][_len-i-1] =temp[i][j]\n",
    "\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        n = len(matrix)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]\n",
    "\n",
    "        for i in range(n):\n",
    "            matrix[i][:] = matrix[i][::-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        tmp=copy.deepcopy(matrix)\n",
    "        n=len(matrix)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                matrix[j][n-1-i]=tmp[i][j]\n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# leetcode submit region begin(Prohibit modification and deletion)\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        # 特判小矩阵\n",
    "        if len(matrix) <= 1:\n",
    "            return matrix\n",
    "\n",
    "        # 标记一圈的起点\n",
    "        strow, stcol = 0, 0\n",
    "        # 记录圈的大小\n",
    "        edgelen = len(matrix) - 1\n",
    "        loopt = len(matrix) // 2\n",
    "        ctr = 0\n",
    "        while ctr < loopt:\n",
    "            inner_ctr = 0\n",
    "            while inner_ctr < edgelen:\n",
    "                r1, c1 = strow, stcol + inner_ctr\n",
    "                r2, c2 = strow + inner_ctr, stcol + edgelen\n",
    "                r3, c3 = strow + edgelen, stcol + edgelen - inner_ctr\n",
    "                r4, c4 = strow + edgelen - inner_ctr, stcol\n",
    "                # print((r1, c1), (r2, c2), (r3, c3), (r4, c4))\n",
    "                matrix[r1][c1], matrix[r2][c2], matrix[r3][c3], matrix[r4][c4] = matrix[r4][c4], matrix[r1][c1], matrix[r2][c2], matrix[r3][c3]\n",
    "                inner_ctr += 1\n",
    "            ctr += 1\n",
    "            strow += 1\n",
    "            stcol += 1\n",
    "            edgelen -= 2\n",
    "# leetcode submit region end(Prohibit modification and deletion)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        length = len(matrix)\n",
    "        matrix[:] = matrix[::-1]\n",
    "\n",
    "        for i in range(length):\n",
    "            for j in range(i):\n",
    "                matrix[j][i], matrix[i][j] = matrix[i][j], matrix[j][i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        for i in range(n//2):\n",
    "            for j in range(n):\n",
    "                matrix[i][j],matrix[n-i-1][j] = matrix[n-i-1][j],matrix[i][j]\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        n = len(matrix)\n",
    "        for i in range(n // 2):\n",
    "            for j in range(n):\n",
    "                matrix[i][j], matrix[n-i-1][j] = matrix[n-i-1][j], matrix[i][j]\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]\n",
    "        return matrix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        # 水平翻转\n",
    "        for i in range(n//2):\n",
    "            for j in range(n):\n",
    "                tmp = matrix[i][j]\n",
    "                matrix[i][j] = matrix[n-1-i][j]\n",
    "                matrix[n-1-i][j] = tmp\n",
    "        # 对角线翻转\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                tmp = matrix[i][j]\n",
    "                matrix[i][j] = matrix[j][i]\n",
    "                matrix[j][i] = tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        for i in range(n // 2):\n",
    "            t = matrix[i]\n",
    "            matrix[i] = matrix[n - 1 - i]\n",
    "            matrix[n - 1 - i] = t\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                t = matrix[i][j]\n",
    "                matrix[i][j] = matrix[j][i]\n",
    "                matrix[j][i] = t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        l = len(matrix)\n",
    "        mid = l // 2\n",
    "        if l % 2 == 0:\n",
    "            bias = 0\n",
    "        else:\n",
    "            bias = 1\n",
    "        for i in range(mid):\n",
    "            for j in range(mid+bias):\n",
    "                matrix[i][j],matrix[j][l-i-1],matrix[l-i-1][l-j-1],matrix[l-j-1][i] = matrix[l-j-1][i],matrix[i][j], matrix[j][l-i-1],matrix[l-i-1][l-j-1]\n",
    "        '''if l % 2 == 1:\n",
    "            for i in range(mid):\n",
    "                matrix[i][mid],matrix[mid][l-i-1],matrix[l-i-1][mid],matrix[mid][i] = matrix[mid][i],matrix[i][mid], matrix[mid][l-i-1],matrix[l-i-1][mid]'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        l = len(matrix)\n",
    "        mid = l // 2\n",
    "        for i in range(mid):\n",
    "            for j in range(mid):\n",
    "                matrix[i][j],matrix[j][l-i-1],matrix[l-i-1][l-j-1],matrix[l-j-1][i] = matrix[l-j-1][i],matrix[i][j], matrix[j][l-i-1],matrix[l-i-1][l-j-1]\n",
    "                '''\n",
    "                matrix[i][j], matrix[j][l-i-1] = matrix[j][l-i-1], matrix[i][j]\n",
    "                matrix[l-i-1][l-j-1], matrix[l-j-1][i] = matrix[l-j-1][i], matrix[l-i-1][l-j-1]\n",
    "                matrix[i][j], matrix[l-i-1][l-j-1] = matrix[l-i-1][l-j-1], matrix[i][j]\n",
    "                '''\n",
    "        if l % 2 == 1:\n",
    "            for i in range(mid):\n",
    "                matrix[i][mid],matrix[mid][l-i-1],matrix[l-i-1][mid],matrix[mid][i] = matrix[mid][i],matrix[i][mid], matrix[mid][l-i-1],matrix[l-i-1][mid]\n",
    "                '''\n",
    "                '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        matrix[:]=zip(*matrix[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        for i in range(n // 2):\n",
    "            for j in range((n+1)//2):\n",
    "                matrix[i][j], matrix[n-j-1][i], matrix[n-i-1][n-j-1], matrix[j][n-i-1] =\\\n",
    "                 matrix[n-j-1][i], matrix[n-i-1][n-j-1], matrix[j][n-i-1], matrix[i][j]\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        N = len(matrix)\n",
    "        irow = 0\n",
    "        while irow<N:\n",
    "            icol = irow+1\n",
    "            while icol<N:\n",
    "                temp = matrix[irow][icol]\n",
    "                matrix[irow][icol] = matrix[icol][irow]\n",
    "                matrix[icol][irow] = temp\n",
    "                icol += 1\n",
    "            irow+=1\n",
    "        midcol = N // 2\n",
    "        icol = 0\n",
    "        while icol<midcol:\n",
    "            irow = 0\n",
    "            while irow<N:\n",
    "                temp = matrix[irow][icol]\n",
    "                matrix[irow][icol] = matrix[irow][N-1-icol]\n",
    "                matrix[irow][N-1-icol] = temp\n",
    "                irow += 1\n",
    "            icol += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        ln=len(matrix)\n",
    "        #更新的圈数\n",
    "        cn=ln//2\n",
    "        for i in range(cn):\n",
    "            for j in range(i,ln-i-1):\n",
    "                tmp=matrix[j][ln-1-i]\n",
    "                matrix[j][ln-1-i]=matrix[i][j]\n",
    "                matrix[i][j]=matrix[ln-1-j][i]\n",
    "                matrix[ln-1-j][i]=matrix[ln-1-i][ln-1-j]\n",
    "                matrix[ln - 1 - i][ln-1-j]=tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        lens = len(matrix)\n",
    "        temp = copy.deepcopy(matrix)\n",
    "        for i in range(lens):\n",
    "            for j in range(lens):\n",
    "                matrix[i][j] = temp[lens - j - 1][i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        N = len(matrix)\n",
    "        for i in range(N//2):\n",
    "                matrix[i], matrix[N-1-i] = matrix[N-1-i], matrix[i]\n",
    "\n",
    "        for i in range(N):\n",
    "            for j in range(i):\n",
    "                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        mymatrix=[[0]*len(matrix) for i in range(len(matrix))]\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix)):\n",
    "                mymatrix[j][len(matrix)-i-1]=matrix[i][j]\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix)):\n",
    "                matrix[i][j]=mymatrix[i][j]\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        for i in range(n // 2):\n",
    "            for j in range((n+1) // 2):\n",
    "                tmp = matrix[i][j]\n",
    "                matrix[i][j] = matrix[n-1-j][i]\n",
    "                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]\n",
    "                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]\n",
    "                matrix[j][n - 1 - i] = tmp\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n=len(matrix)\n",
    "        matrixNew=[[0]*n for i in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                matrixNew[j][n-1-i]=matrix[i][j]\n",
    "        matrix[:]=matrixNew"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import ceil, floor\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        l = len(matrix)\n",
    "\n",
    "        if l % 2 == 1:\n",
    "            for i in range(0, ceil(l / 2)):\n",
    "                for j in range(0, floor(l / 2)):\n",
    "                    x,y = i,j\n",
    "                    temp = matrix[x][y]\n",
    "                    for _ in range(4):\n",
    "                        matrix[y][l-1-x], temp = temp, matrix[y][l-1-x]\n",
    "                        x,y = y, l-1-x\n",
    "\n",
    "        else:\n",
    "            for i in range(0, ceil(l / 2)):\n",
    "                for j in range(0, floor(l / 2)):\n",
    "                    x,y = i,j\n",
    "                    temp = matrix[x][y]\n",
    "                    for _ in range(4):\n",
    "                        matrix[y][l-1-x], temp = temp, matrix[y][l-1-x]\n",
    "                        x,y = y, l-1-x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        for i in range((n+1)//2):\n",
    "            for j in range((n)//2):\n",
    "                tmp = matrix[i][j]\n",
    "                matrix[i][j] = matrix[n-1-j][i]\n",
    "                matrix[n-1-j][i] = matrix[n-1-i][n-1-j]\n",
    "                matrix[n-1-i][n-1-j] = matrix[j][n-1-i]\n",
    "                matrix[j][n-1-i] = tmp\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead\n",
    "        \"\"\"\n",
    "        n=len(matrix)\n",
    "        dp=[[0 for i in range(n)] for j in range(n)]\n",
    "     \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                dp[j][n-i-1]=matrix[i][j]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                matrix[i][j]=dp[i][j]\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        matrix[:]=list(zip(*matrix[::-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(i):\n",
    "                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]\n",
    "\n",
    "        for i in range(len(matrix)):\n",
    "            matrix[i] = matrix[i][::-1]\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        matrix[:]=zip(*matrix[::-1])\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "   \"\"\"\n",
    "        n = len(matrix)\n",
    "        for i in range(n // 2):\n",
    "            for j in range((n + 1) // 2):\n",
    "                matrix[i][j], matrix[n - j - 1][i], matrix[n - i - 1][n - j - 1], matrix[j][n - i - 1] \\\n",
    "                    = matrix[n - j - 1][i], matrix[n - i - 1][n - j - 1], matrix[j][n - i - 1], matrix[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        n = len(matrix)\n",
    "\n",
    "        \n",
    "        for i in range(n//2):\n",
    "            for j in range((n+1)//2):\n",
    "                # print((i,j), (n-j-1, n-i-1),(n-i-1,j), (n-j-1,i))\n",
    "                # print(matrix[i][j],matrix[n-j-1][n-i-1],matrix[n-i-1][j],matrix[n-j-1][i])\n",
    "                matrix[i][j], matrix[n-j-1][i], matrix[n-i-1][n-j-1], matrix[j][n-i-1] = matrix[n-j- 1][i], matrix[n-i-1][n-j-1], matrix[j][n-i-1], matrix[i][j]\n",
    " \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        matrix[:]=zip(*matrix[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        matrix[:]=zip(*matrix[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        r, c = len(matrix), len(matrix[0])\n",
    "        \n",
    "        if r == 0 or r == 1:\n",
    "            return matrix\n",
    "        \n",
    "        # 上下翻转\n",
    "        for i in range(r // 2):\n",
    "            for j in range(c):\n",
    "                matrix[i][j], matrix[r-i-1][j] = matrix[r-i-1][j], matrix[i][j]\n",
    "        # 主对角线翻转\n",
    "        for i in range(r):\n",
    "            for j in range(i):\n",
    "                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]\n",
    "        \n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        matrix[:] = zip(*matrix[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        matrix[:] =[row[::-1] for row in zip(*matrix)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix) -> None:\n",
    "        n = len(matrix[0])\n",
    "        j = 0\n",
    "        for i in range(0, n):\n",
    "            matrix[i].reverse()\n",
    "        #print('m1 = ', matrix)\n",
    "        i = 0\n",
    "        for i in range(0, n-1):\n",
    "            for j in range(0, n-i):\n",
    "                \n",
    "                temp = matrix[i][j]\n",
    "                matrix[i][j] = matrix[n-j-1][n-i-1]\n",
    "                matrix[n-j-1][n-i-1] = temp\n",
    "        #print('m2 = ', matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        r = len(matrix)\n",
    "        c = len(matrix[0])\n",
    "        # transpose\n",
    "        temp = [[0] * c for _ in range(r)]\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                temp[j][i] = matrix[i][j]\n",
    "        \n",
    "        for i in range(len(temp)):\n",
    "            for j in range(len(temp[0])):\n",
    "                matrix[i][j] = temp[i][len(temp[0]) - 1 - j]\n",
    "\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        Num = len(matrix)\n",
    "        for i in range(Num):\n",
    "            for j in range(i):\n",
    "                matrix[i][j], matrix[j][i] =  matrix[j][i], matrix[i][j]\n",
    "        for i in range(Num):\n",
    "            matrix[i][:] = matrix[i][::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        tmp = copy.deepcopy(matrix)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                matrix[j][n - 1 - i] = tmp[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        n = len(matrix)\n",
    "        # 深拷贝 matrix -> tmp\n",
    "        tmp = copy.deepcopy(matrix)\n",
    "        # 根据元素旋转公式，遍历修改原矩阵 matrix 的各元素\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                matrix[j][n - 1 - i] = tmp[i][j]\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        n = len(matrix)\n",
    "        # Python 这里不能 matrix_new = matrix 或 matrix_new = matrix[:] 因为是引用拷贝\n",
    "        matrix_new = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                matrix_new[j][n - i - 1] = matrix[i][j]\n",
    "        # 不能写成 matrix = matrix_new\n",
    "        matrix[:] = matrix_new\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        r = len(matrix)\n",
    "        c = len(matrix[0])\n",
    "        # transpose\n",
    "        temp = [[0] * c for _ in range(r)]\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                temp[j][i] = matrix[i][j]\n",
    "        \n",
    "        for i in range(len(temp)):\n",
    "            for j in range(len(temp[0])):\n",
    "                matrix[i][j] = temp[i][len(temp[0]) - 1 - j]\n",
    "\n",
    "        return matrix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        # 旋转矩阵 \n",
    "        # 给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。\n",
    "        # 不占用额外内存空间能否做到？\n",
    "        \"\"\"\n",
    "        [1],[2],[3],[4],5\n",
    "        2 ,[3],[4], 5,6\n",
    "        3 ,4 ,5 ,6,7   ---->[倒三角顺时针旋转，【】标识待旋转的元素，[0,4]=[1,3]=[2,2]=5这些个元素不用旋转]\n",
    "        4 ,5 ,6 ,7,8   \n",
    "        5 ,6 ,7 ,8,9\n",
    "        \"\"\"\n",
    "        def exchange(matrix : list[list[int]], x1 : int, y1 : int, x2 : int, y2 : int) -> None:\n",
    "            # 不占用额外内存的情况下，更换matrix[x1][y1]与matrix[x2][y2]的值：\n",
    "            # a = a + b\n",
    "            # b = a - b = (a + b) - b = a\n",
    "            # a = a - b = (a + b) - a = b\n",
    "            matrix[x1][y1] = matrix[x1][y1] + matrix[x2][y2]\n",
    "            matrix[x2][y2] = matrix[x1][y1] - matrix[x2][y2]\n",
    "            matrix[x1][y1] = matrix[x1][y1] - matrix[x2][y2]\n",
    "\n",
    "        num = len(matrix)\n",
    "        for i in range(num):\n",
    "            j = i\n",
    "            while j < num - 1 - i:\n",
    "                exchange(matrix, i, j, j, num - 1 - i)\n",
    "                exchange(matrix, i, j, num - 1 - i, num - 1 - j)\n",
    "                exchange(matrix, i, j, num - 1 - j, i)\n",
    "                j += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        matrix[:]=zip(*matrix[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range (len(matrix)-1):\n",
    "            for j in range (i+1,len(matrix)):\n",
    "                matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]\n",
    "        for i in range (len(matrix)):\n",
    "            matrix[i]=matrix[i][::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        l=len(matrix)\n",
    "        c=int(l/2)\n",
    "        for i in range(c):\n",
    "          matrix[i],matrix[l-1-i]=matrix[l-1-i],matrix[i]\n",
    "        for i in range(l):\n",
    "            for j in range(i):\n",
    "              matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        matrix[:] = zip(*matrix[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        matrix.reverse()\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(i+1,len(matrix)):\n",
    "                a=matrix[i][j]\n",
    "                matrix[i][j]=matrix[j][i]\n",
    "                matrix[j][i]=a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        matrix[::]=zip(*matrix[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        matrix[:] = zip(*matrix[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        temp=0;n=len(matrix)\n",
    "        for i in range(n//2):\n",
    "            for j in range((n+1)//2): #只进行一半的\n",
    "                temp=matrix[i][j]\n",
    "                matrix[i][j]=matrix[n-1-j][i]\n",
    "                matrix[n-1-j][i]=matrix[n-1-i][n-1-j]\n",
    "                matrix[n-1-i][n-1-j]=matrix[j][n-1-i]\n",
    "                matrix[j][n-1-i]=temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        row_len=len(matrix)\n",
    "        col_len=len(matrix[0])\n",
    "        for r in range(row_len):\n",
    "            for c in range(r):\n",
    "                matrix[r][c],matrix[c][r]=matrix[c][r],matrix[r][c]\n",
    "        \n",
    "        for i in range(row_len):\n",
    "            matrix[i][:]=matrix[i][::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[ [1,2,3], [4,5,6], [7,8,9] ]\n",
    "[ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ]\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        if not matrix: return\n",
    "        n = len(matrix)\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]\n",
    "        for i in range(n):\n",
    "            a, b = 0, n-1\n",
    "            while a < b:\n",
    "                matrix[i][b], matrix[i][a] = matrix[i][a], matrix[i][b]\n",
    "                a += 1\n",
    "                b -= 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
